package splay;

class NoSplay{
	
	protected int key = -1;
	protected NoSplay left;
	protected NoSplay right;
	protected NoSplay parent;
	
	public boolean isEmpty(){
		return this.key == -1;
	}
	
	public boolean isLeaf(){
		return this.key != -1 && this.left.isEmpty() && this.right.isEmpty();
	}
	
	public int getKey() {
		return key;
	}
	public void setKey(int key) {
		this.key = key;
	}
	public NoSplay getLeft() {
		return left;
	}
	public void setLeft(NoSplay left) {
		this.left = left;
	}
	public NoSplay getRight() {
		return right;
	}
	public void setRight(NoSplay right) {
		this.right = right;
	}
	public NoSplay getParent() {
		return parent;
	}
	public void setParent(NoSplay parent) {
		this.parent = parent;
	}
}

public interface SplayTree {
		

	/**
	 * Retorna a altura de uma arvore.
	 * @return
	 */
	public int height();
	
	/**
	 * Busca um valor associado a uma dada chave na arvore. Retorna null caso 
	 * nao esteja na arvore.
	 * @param chave
	 * @return
	 */
	public NoSplay search(int key);
	
	/**
	 * Insere um valor value associado a uma chave key numa arvore.
	 * @param key
	 * @param value
	 */
	public void insert(int key);
	
	
	/**
	 * Deleta o no que contem dados e a chave dada.
	 * @param key
	 */
	public void delete(int key);
	
	/**
	 * Retorna uma string contendo as chaves da arvore em pre-ordem, 
	 * separadas por um espaco. Note que nesse metodo o ultimo
	 * caractere deve ser o espaco em branco. Assim, a sequencia no final sempre tem 
	 * um espaco em branco. Exemplo, suponha que uma arvore splay guarda os nos 
	 * 1,14 e 25. A string listando os nos em pre-ordem eh dada por "1 14 25 "
	 */
	public String preOrder();
	
	
	/**
	 * Retorna a quantidade de nos da arvore que contem dados satelites (nao vazios).
	 * @return
	 */
	public int size();
}
